package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
 *
 * 请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
 *
 * 给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-if-path-exists-in-graph
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1971 {

    // 广度优先，可以考虑并查集
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] t = new List[n];

        for (int i = 0;i<n;i++){
            t[i] = new ArrayList<>();
        }
        for (int[] edge:edges) {
            int x = edge[0];
            int y = edge[1];
            t[x].add(y);
            t[y].add(x);
        }
        boolean[] visit = new boolean[n];
        visit[source] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            if (poll == destination) {
                break;
            }
            List<Integer> list = t[poll];
            for (Integer i:list) {
                if (!visit[i]) {
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
        return visit[destination];
    }
}
